package com.springboot.demo.sort;

/**
 * 希尔排序，不稳定
 *
 * <p>
 * 算法思想：
 * <p>
 * 1、将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。
 * <p>
 * 2、再取k=k/2 ，将下标差值为k的数分为一组，构成有序序列。
 * <p>
 * 3、重复第二步，直到k=1执行简单插入排序。
 *
 * 时间复杂度：o(nlogn)
 * 空间复杂度：o(1)
 *
 * @author supu
 * @date 2019-12-12 10:46
 **/
public class HillSort {
    public static void hillSort(int[] a) {
        int groupNumber = a.length;
        while (groupNumber != 0) {
            // 分组数
            groupNumber = groupNumber / 2;
            // 插入次数
            for (int x = 0; x < groupNumber; x++) {
                // 要插入的数组数
                for (int i = x + groupNumber; i < a.length; i += groupNumber) {
                    // 要插入的数
                    int insertNumber = a[i];
                    // 目前排好序的最大数的位置
                    int j = i - groupNumber;
                    while (j >= 0 && a[j] > insertNumber) {
                        a[j + groupNumber] = a[j];
                        j -= groupNumber;
                    }
                    a[j + groupNumber] = insertNumber;
                }
            }
        }
    }

    public static void hillSort1(int[] a){
        /*int group = a.length;
        while (group != 0){
            group = group / 2;
            // 插入次数
            for (int i = 0; i < group; i++) {
                for (int j = i + group; j < a.length; j+=group) {
                    int insertNum = a[j];
                    int m = j - group;
                    while (m >= 0 && a[m] > insertNum) {
                        a[m+group] = a[m];
                        m-=group;
                    }
                    a[m+group] = insertNum;
                }
            }
        }*/
        int group = a.length;
        while (group != 0){
            group = group / 2;
            for (int i = 0; i < group; i++) {
                for (int j = i + group; j < a.length; j+=group) {
                    int insertNum = a[j];
                    int k = j - group;
                    while (k >= 0 && a[k] > insertNum){
                        a[k+group] = a[k];
                        k-=group;
                    }
                    a[k+group] = insertNum;
                }
            }
        }
    }
}
